//package com.cwj;
//
//import java.util.Arrays;
//import java.util.HashMap;
//import java.util.Map;
//
//
///**
// * 可统计大小的并查集
// */
//public class UnionFind {
//
//    int[] parent;
//    int[] sz;
//
//    public UnionFind(int n) {
//        parent = new int[n];
//        sz = new int[n];
//        Arrays.fill(sz, 1);
//        for (int i = 0; i < n; i++) {
//            parent[i] = i;
//        }
//    }
//
//    public void union(int x, int y) {
//        int s = find(y);
//        int f = find(x);
//        int ss = s,ff = f;
//        if(sz[s] > sz[f]) {
//            ff = s;
//            ss = f;
//        }
//        parent[ss] = ff;
//        sz[ff] += sz[ss];
//    }
//
//    public int find(int x) {
//        return x == parent[x] ? x : (parent[x] = find(parent[x]));
//    }
//
//    public int getCnt(int x) {
//        return sz[find(x)];
//    }
//}
//
//class UnionFindMap {
//
//    Map<Integer, Integer> map = new HashMap<>();
//
//    public void union(int x, int y) {
//        if (!map.containsKey(x)) {
//            map.put(x, x);
//        }
//        if (!map.containsKey(y)) {
//            map.put(y, y);
//        }
//        map.put(find(x), find(y));
//    }
//
//    public int find(int x) {
//        return x == map.get(x) ? x : find(map.get(x));
//    }
//}
